package com.strindex.kmp;


import java.util.Arrays;

/**
 * ClassName: KmpMain
 * Description:
 *
 * @author kang.wang03
 *         Date 2016/11/22
 */
public class KmpMain {
    public static void main(String args[]) {
        String str = "abcdefcefgeabcdabd";
        System.out.println(Arrays.toString(getNext("abcdabd")));
        System.out.println(kmSearch(str,"abcdabd"));
    }

    private static int kmSearch(String source, String target) {
        int i = 0;
        int j = 0;
        int sLen = source.length();
        int pLen = target.length();
        char[] s = source.toCharArray();
        char[] p = target.toCharArray();
        int next[] = getNext(source);
        while (i < sLen && j < pLen) {
            //如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
            if (j == -1 || s[i] == p[j]) {
                i++;
                j++;
            } else {
                //如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
                //next[j]即为j所对应的next值
                j = next[j];
            }
        }
        if (j == pLen)
            return i - j;
        else
            return -1;
    }

    private static int[] getNext(String str) {
        int length = str.length();
        char p[] = str.toCharArray();
        int next[] = new int[length];
        next[0] = -1;
        int k = -1;
        int j = 0;
        while (j < length - 1) {
            //p[k]表示前缀，p[j]表示后缀
            if (k == -1 || p[j] == p[k]) {
                ++k;
                ++j;
                next[j] = k;
            } else {
                k = next[k];
            }
        }
        return next;
    }
}
